743. 网络延迟时间

为保证权益，题目请参考 743. 网络延迟时间(From LeetCode).

解决方案1

Python

# 743. 网络延迟时间
# https://leetcode-cn.com/problems/network-delay-time/

from typing import List
import heapq


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # getD
        d = {}
        for i in range(1, n + 1):
            d[i] = []
        for ti in times:
            d[ti[0]].append([ti[1], ti[2]])

        dis = [100000000] * (n + 1)
        dis[k] = 0

        q = [[0, k]]
        heapq.heapify(q)
        while len(q) != 0:
            t = heapq.heappop(q)
            if t[0] > dis[t[1]]:
                continue

            for tar, di in d[t[1]]:
                if dis[tar] > dis[t[1]] + di:
                    dis[tar] = dis[t[1]] + di
                    heapq.heappush(q, [dis[tar], tar])

        mm = 0
        for i in range(1, len(dis)):
            mm = max(mm, dis[i])

        return mm if mm != 100000000 else -1


if __name__ == "__main__":
    solution = Solution()
    print(solution.networkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2))

解决方案2

Python

import heapq
from typing import List


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        nexts = dict()
        for i in range(n + 1):
            nexts[i] = []
        for x,y,z in times:
            nexts[x].append((y, z))

        pq = [[0, k]]
        heapq.heapify(pq)

        MAX_INF: int = 99999999999
        dist = [MAX_INF] * (n + 1)
        dist[k] = 0

        while len(pq) > 0:
            d, t = heapq.heappop(pq)

            for y, z in nexts[t]:
                if d + z < dist[y]:
                    dist[y] = d + z
                    pq.append([dist[y], y])

        ans = 0
        for i in range(1, n + 1):
            if dist[i] == MAX_INF:
                return -1
            ans = max(ans, dist[i])
        return ans

so = Solution()
print(so.networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))